package q779_kthGrammar;

public class Solution_1 {
    /*
    第K个语法符号
    最简单的方法：
    由于第n行的数是由第n - 1行的某个数生成的
    因此回溯即可
    第k个数应由(k + 1) / 2的数字生成
    然后判断当前k是否是一个偶数或者奇数
    分别有不同的生成结果
     */
    public int kthGrammar(int n, int k) {
        if (n == 0) return 0;
        return (k & 1) ^ 1 ^ kthGrammar(n - 1, (k + 1) / 2);
    }
}
